Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100
Average Rating: 4.75 (67 votes)
Video Solution
Solution Article
Overview
The problem is similar to the classic Knapsack problem. The basic idea is to understand that to partition an array into two subsets of equal sum say subSetSum, the totalSum of given array must be twice the subSetSum
totalSum=subSetSum∗2
This could also be written as, subSetSum=totalSum/2
Example Assume totalSum of an array is 20 and if we want to partition it into 2 subsets of equal sum, then the subSetSum must be (20/2)=10.
Now, the problem to find the subset with a sum equals a given target. Here target is subSetSum.
It must be noted that the total sum of an array must be even, only then we can divide it into 2 equal subsets. For instance, we cannot have an equal subSetSum for an array with total sum as 21.
Note:
Finding a subset with a sum equal to a given target is different than Subarray sum equals k. Subarray is a contiguous sequence of array elements, whereas the subset could consist of any array elements regardless of the sequence. But each array element must belong to exactly one subset.
Let's discuss different algorithms to find the subset with a given sum.
Approach 1: Brute Force
Intuition
We have to find a subset in an array where the sum must be equal to subSetSum that we calculated above. The brute force approach would be to generate all the possible subsets of an array and return true if we find a subset with the required sum.
Algorithm
Assume, there is an array nums of size n and we have to find if there exists a subset with total sum=subSetSum. For a given array element x, there could be either of 2 possibilities:
-
Case 1) x is included in subset sum. subSetSum=subSetSum−x
-
Case 2) x is not included in subset sum, so we must take previous sum without x. subSetSum=subSetSum
We can use depth first search and recursively calculate the subSetSum for each case and check if either of them is true. This can be formulated as
isSum (subSetSum, n) = isSum(subSetSum- nums[n], n-1) || isSum(subSetSum, n-1)
Base Cases
- If subSetSum is 0, return true ( Since we found a subset with sum subSetSum )
- If subSetSum is less than 0, return false
Complexity Analysis
-
Time Complexity : O(2n), where n is equal to number of array elements. The recursive solution takes the form of a binary tree where there are 2 possibilities for every array element and the maximum depth of the tree could be n. The time complexity is exponential, hence this approach is exhaustive and results in Time Limit Exceeded (TLE).
-
Space Complexity: O(N) This space will be used to store the recursion stack. We can’t have more than n recursive calls on the call stack at any time.
Approach 2: Top Down Dynamic Programming - Memoization
Intuition
In the above approach, we observe that the same subproblem is computed and solved multiple times.
Example :
In the above recursion tree, we could see that isSum(3,[6]) is computed twice and the result is always the same. Since the same subproblem is computed again and again, the problem has Overlapping Subproblem property and can be solved using Dynamic Programming.
Algorithm
We could have stored the results of our computation for the first time and used it later. This technique of computing once and returning the stored value is called memoization. We use a two dimensional array memo and follow the following steps for each recursive call :
- Check if subSetSum for a given n exists in memo to see if we can avoid computing the answer and return the result stored in memo.
- Save the results of any calculations to memo.
Complexity Analysis
Let n be the number of array elements and m be the subSetSum.
-
Time Complexity : O(m⋅n).
-
In the worst case where there is no overlapping calculation, the maximum number of entries in the
memowould be m⋅n. For each entry, overall we could consider that it takes constant time, i.e. each invocation ofdfs()at most emits one entry in thememo. -
The overall computation is proportional to the number of entries in
memo. Hence, the overall time complexity is O(m⋅n).
-
-
Space Complexity: O(m⋅n). We are using a 2 dimensional array memo of size (m⋅n) and O(n) space to store the recursive call stack. This gives us the space complexity as O(n) + O(m⋅n) = O(m⋅n)
Approach 3: Bottom Up Dynamic Programming
Intuition
This is another approach to solving the Dynamic Programming problems. We use the iterative approach and store the result of subproblems in bottom-up fashion also known as Tabulation.
Algorithm
We maintain a 2D array , dp[n][subSetSum] For an array element i and sum j in array nums,
dp[i][j]=true if the sum j can be formed by array elements in subset nums[0]..nums[i],otherwise dp[i][j]=false
dp[i][j] is true it satisfies one of the following conditions :
- Case 1) sum j can be formed without including ith element,
if dp[i−1][j]==true
- Case 2) sum j can be formed including ith element,
if dp[i−1][j−nums[i]]==true
Complexity Analysis
-
Time Complexity : O(m⋅n), where m is the subSetSum, and n is the number of array elements. We iteratively fill the array of size m⋅n.
-
Space Complexity : O(m⋅n) , where n is the number of array elements and m is the subSetSum. We are using a 2 dimensional array dp of size m⋅n
Approach 4: Optimised Dynamic Programming - Using 1D Array
Intuition
We could further optimize Approach 3. We must understand that for any array element i, we need results of the previous iteration (i-1) only. Hence, we could achieve the same using a one-dimensional array as well.
Complexity Analysis
-
Time Complexity : O(m⋅n), where m is the subSetSum, and n is the number of array elements. The time complexity is the same as Approach 3.
-
Space Complexity: O(m), As we use an array of size m to store the result of subproblems.
Note:
The overall performance of Approach 2 is better than all the approaches discussed above. This is because we terminate our search as soon as we find a subset with the required sum. Hence, it performs better in most cases except for the worst case.
Why iterate from back in Approach 4? iterating from starting is giving WA
for (int j = subSetSum; j >= curr; j--)
Last Edit: November 3, 2020 9:12 AM
Due to nature of this problem, it is possible that there are no overlapping subproblems as well. Example, when all the numbers are odd. [7,5,3,1], sum = 16, subset sum = 8. The recursion tree would be
It is evident that none of the subproblems overlap.
In such cases the memoization approach (Approach 2) would have same time complexity as Approach 1.
@caitao @dev_ps @rexhu100
August 27, 2020 9:11 PM
The memoization approach should have the same time complexity as the bottom-up DP approach.
Last Edit: September 2, 2020 11:44 AM
Can anyone explain in Solution 2, why do we only use subSetSum as the key of the memo?
I think it should be a pair of (subSetSum, n).
The solution doesn't work when I switch the order of
boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1]) || dfs(nums, n - 1, subSetSum);
to
boolean result = dfs(nums, n - 1, subSetSum) || dfs(nums, n - 1, subSetSum - nums[n - 1]);
Well explained!!!. I have one doubt though
Why we are subtracting nums[n-1] here?
boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1], memo) ||
dfs(nums, n - 1, subSetSum, memo);
According to the recursion equation, recursive call should be like this
boolean result = dfs(nums, n - 1, subSetSum - nums[n], memo) ||
dfs(nums, n - 1, subSetSum, memo); // since we are calling the function with index n-1.
Since we are deducting the value at n-1th index, I am wondering how this solution is working for not considering the current value which is at index 'n'?
In approach 1 and 2, the code for recurrence calls is not correct for the subsetSum problem in general (where the target may be any number).
It never takes nums[n-1] into consideration while calculating the subset sum.
First input to dfs() is newN=n-1. Then, nums[newN-1] (=n-1-1 =n-2) is subtracted from subSetSum.
It happens to works for this problem since the target is sum/2.
In this problem, there must be 0 or 2 subsets with the same sum as target (total sum = target+target).
So even if the subset containing nums[n-1] is missed, the other subset is found and it will return true.
The new video Leetcode provides explains everything clearly and concisely. This is an awesome addition and hopefully we can see this kind of solution more.
"The problem is similar to the classic Knapsack problem": I don't get it...
September 10, 2020 10:27 AM
This is the python3 version of approach 3
class Solution:
def canPartition(self, nums: List[int]) -> bool:
totalSum = sum(nums)
if totalSum % 2 != 0: return False
subSetSum = totalSum // 2
n = len(nums)
dp = [[False] * (subSetSum+1) for _ in range(n+1)]
dp[0][0] = True
for i in range(1, n+1):
curr = nums[i-1]
for j in range(subSetSum+1):
if j < curr:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-curr]
return dp[n][subSetSum]
Last Edit: September 13, 2020 8:09 AM
I don't understand why the memoization is in this form: unordered_map<int, bool> memo;
the recursion function is getting called with a specific index and subsetSum: bool dfs(vector<int> &nums, int n, int subSetSum)
So why the memoization memo does not need to be associated with an index at all? I am really confused about this.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/18/2021 19:49 | Accepted | 252 ms | 11.8 MB | cpp |
| 06/18/2021 19:47 | Accepted | 300 ms | 75.9 MB | cpp |
| 03/27/2021 08:26 | Accepted | 96 ms | 11.2 MB | cpp |
| 03/16/2021 13:50 | Accepted | 96 ms | 11.3 MB | cpp |
| 08/29/2020 16:33 | Accepted | 60 ms | 9.5 MB | cpp |
| 08/29/2020 16:32 | Accepted | 56 ms | 9.6 MB | cpp |
| 08/29/2020 16:32 | Wrong Answer | N/A | N/A | cpp |
x
class Solution {public: bool canPartition(vector<int>& nums) { int n = nums.size(); int sum = 0; for(int i=0;i<nums.size();i++) { sum += nums[i]; } if(sum%2 != 0) return false; int target = sum/2; vector<vector<bool>> dp(n+1, vector<bool>(target+1, 0)); for(int i=0;i<=n;i++) { for(int j=0;j<=target;j++) { if(i == 0) dp[i][j] = false; if(j == 0) dp[i][j] = true; } } for(int i=1;i<=n;i++) { for(int j=1;j<=target;j++) { if(nums[i-1] <= j) dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j]; else dp[i][j] = dp[i-1][j]; } } return dp[n][target]; }};
